package com.ting.test.algorithms.大厂刷题班;

/**
 * 给定一个二维数组arr 可以从任意一个位置出发
 * 可以走上下左右
 * 返回可以走出来的最长递增链路长度
 */
public class 二维数组中最长递增的路径长度 {
    public static void main(String[] args) {
        int[][] arr = new int[][]{};

        int length = process(arr);

    }

    private static int process(int[][] arr) {
        if (arr == null) {
            return 0;
        }

        int max = 0;

        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                int length = f(arr, i, j);
                max = Math.max(max, length);
            }
        }
        return max;
    }

    /**
     * 该函数的含义是从i,j位置出发，获得的最大递增链路的长度
     *
     * @param arr
     * @param i
     * @param j
     * @return
     */
    private static int f(int[][] arr, int i, int j) {
        int up = i > 0 ? f(arr, i - 1, j) : 0;
        int down = i < arr.length ? f(arr, i + 1, j) : 0;
        int left = j > 0 ? f(arr, i, j - 1) : 1;
        int right = j < arr[0].length ? f(arr, i, j + 1) : 0;
        return Math.max(Math.max(up, down), Math.max(left, right));
    }

    /**
     * 该函数的含义是从i,j位置出发，获得的最大递增链路的长度
     *
     * @param arr
     * @param i
     * @param j
     * @return
     */
    private static int f2(int[][] arr, int i, int j, int[][] dp) {
        if (dp[i][j] != 0) {// 如果该位置已经计算过，那么他最小长度也应该是1，因此如果是0 则表示该位置还没计算，否则计算过
            return dp[i][j];
        }
        int up = i > 0 ? f(arr, i - 1, j) : 0;
        int down = i < arr.length ? f(arr, i + 1, j) : 0;
        int left = j > 0 ? f(arr, i, j - 1) : 1;
        int right = j < arr[0].length ? f(arr, i, j + 1) : 0;
        int maxlength = Math.max(Math.max(up, down), Math.max(left, right));
        dp[i][j] = maxlength;
        return maxlength;
    }
}
